from os import device_encoding, path
from queue import Queue
# 图的邻接矩阵表示法

vertex=5  
class ArcNode:
    def __init__(self,adjvex):
        self.adjvex=adjvex
        self.nextNode=None

class VNode:
    def __init__(self,data):
        self.data=data
        self.firstNode=None
    def __str__(self) -> str:
        return self.data

class AMGraph:
    def __init__(self):
        self.vertices=[]
        self.versNum=vertex
        self.Visited=[0]*5  # 记录访问过后的结点信息

        fileCount=0   # 记录文件的总行数
        with open("./ax1.txt",'r',encoding='utf-8') as f:
            while True:
                text=f.readline()
                if not text:
                    break
                else:
                    fileCount+=1
            f.seek(0,0)
            self.arcsNum=fileCount-self.versNum
            for i in range(self.versNum):
                self.vertices.append(VNode(f.readline().replace('\n','')))
            
            for i in range(self.arcsNum):
                tempchars=f.readline()
                tempx=AMGraph.location(self.vertices,tempchars[0])
                tempy=AMGraph.location(self.vertices,tempchars[2])
                if self.vertices[tempx].firstNode==None:
                    self.vertices[tempx].firstNode=ArcNode(tempy)
                else:
                    tempNode=ArcNode(tempy)
                    tempNode.nextNode=self.vertices[tempx].firstNode
                    self.vertices[tempx].firstNode=tempNode
                
                if self.vertices[tempy].firstNode==None:
                    self.vertices[tempy].firstNode=ArcNode(tempx)
                else:
                    tempNode=ArcNode(tempx)
                    tempNode.nextNode=self.vertices[tempy].firstNode
                    self.vertices[tempy].firstNode=tempNode
    
    def deepSearch(self,index):
        # 深度优先遍历
        self.Visited[index]=1
        print(self.vertices[index].data,end='\t')
        p1=self.vertices[index].firstNode
        while p1!=None:
            if self.Visited[p1.adjvex]!=1:
                self.deepSearch(p1.adjvex)
            p1=p1.nextNode
    
    def spanSearch(self,index):
        # 广度优先遍历--> 队列实现
        self.Visited=[0]*5
        spanQueue=Queue(5)
        spanQueue.put(index)
        self.Visited[index]=1
        while(not spanQueue.empty()):
            index=spanQueue.get()
            print(self.vertices[index].data,end='\t')
            p1=self.vertices[index].firstNode
            while p1!=None:
                if self.Visited[p1.adjvex]!=1:
                    self.Visited[p1.adjvex]=1
                    spanQueue.put(p1.adjvex)
                p1=p1.nextNode

# 计算无向图邻接矩阵表示法中边的度  
    def countTuDegree(self,index):
        count=0
        p1=self.vertices[index].firstNode
        while p1!=None:
            count+=1
            p1=p1.nextNode
        return count

                
    @classmethod
    def location(cls,vertices,c):
        count=0
        for i in vertices:
            if i.data==c:
                return count
            else:
                count+=1
        return count

if __name__=='__main__':
    mygraph=AMGraph()
    mygraph.deepSearch(1)
    print()
    mygraph.spanSearch(1)
    print("\n顶点为a的度:",mygraph.countTuDegree(0))
    print("顶点为b的度:",mygraph.countTuDegree(1))